package main

import (
	"fmt"
	"math"
	"time"
)

// func arrayPrint(grid [][]int) {
// 	for i := 0; i < len(grid); i++ {
// 		fmt.Println(grid[i])
// 	}
// 	return
// }

func shortestPathBinaryMatrix(grid [][]int) int {

	return findPath(grid, 0, 0, 2)
}

func findPath(grid [][]int, r int, c int, step int) int {
	m := len(grid)
	n := len(grid[0])
	// if r < 0 || r > m-1 || c < 0 || c > n-1 {
	// 	return -1
	// }
	// if grid[r][c] == 1 {
	// 	return -1
	// }

	count := 0
	result, each := math.MaxInt32, math.MaxInt32

	if grid[r][c] == 0 || grid[r][c] > step {
		grid[r][c] = step
		//如果最后一个返回
		// fmt.Println("grid,r,c", grid, r, c)
		if r == m-1 && c == n-1 {
			return step - 1
		}
		//判读其他八个方向{1,1}, {0, 1}, {1, 0}, {-1, 1}, {1, -1}, {-1,0}, {0, -1}, {-1, -1}
		// fmt.Println("判断八个方向开始")
		// coordinate := [][]int{{1, 1}, {0, 1}, {1, 0}, {-1, 1}, {1, -1}, {-1, 0}, {0, -1}, {-1, -1}}
		coordinate := [][]int{{1, 1}, {-1, 1}, {1, -1}, {-1, -1}, {0, 1}, {1, 0}, {-1, 0}, {0, -1}}

		for _, v := range coordinate {
			if r+v[0] < 0 || r+v[0] > m-1 || c+v[1] < 0 || c+v[1] > n-1 {
				count++
				continue
			}
			if grid[r+v[0]][c+v[1]] == 1 {
				count++
				continue
			}
			// if grid[r+v[0]][c+v[1]] == 0 && grid[r+v[0]][c+v[1]] > step+1 {
			// 	grid[r+v[0]][c+v[1]] = step + 1
			// }

			// arrayPrint(grid)
			// fmt.Println(v)
			// fmt.Println(result)
			// fmt.Println()
			each = findPath(grid, r+v[0], c+v[1], step+1)
			if each == -1 {
				count++
				continue
			}
			// fmt.Println(result)
			// arrayPrint(grid)
			// fmt.Println()
			if result > each {
				result = each
			}

		}
		if count == 8 {
			return -1
		} else {
			return result

		}

	}
	return -1

}

func main() {
	start := time.Now()
	grid := [][]int{{0, 1}, {1, 0}}
	// grid := [][]int{{0, 1, 0, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 1, 1, 0, 1, 0}, {0, 0, 0, 0, 1, 0}, {1, 1, 1, 1, 1, 0}, {1, 1, 1, 1, 1, 0}}
	// grid := [][]int{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}
	result := shortestPathBinaryMatrix(grid)
	cost := time.Since(start)
	fmt.Println("result:", result)
	fmt.Println(cost)
}
